import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public String tree2str(TreeNode root) {
        if(root == null){
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();//因为要将最终的结果放入到字符串中，所以创建一个StringBulider类型的对象，用来存放遍历到的结果，为什么用StringBulider而不用String是应为，得到的字符，要经行拼接，String类型的对象不能进行拼接。
        tree2strChilde(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChilde(TreeNode t,StringBuilder stringBuilder){//为什么给tree2strChilde方法一个stringBulider形参，原因是每次递归这个方法的时候，将结果都要放入stringBulider字符串中。
        if(t == null){
            return;
        }
        stringBuilder.append(t.val);//将根的值放入
        if(t.left != null){
            stringBuilder.append("(");
            tree2strChilde(t.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            //左边为空，右边不为空
            if(t.right != null){
                stringBuilder.append("()");
            }else{//左边为空，右边为空
                return;

            }
        }
        if(t.right == null){
            return ;
        }else{
            stringBuilder.append("(");
            tree2strChilde(t.right,stringBuilder);
            stringBuilder.append(")");
        }
    }
    //判断二叉树是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if (root == null) {
            return true;//这里认为空树也为完全二叉树
        }
        Queue<TreeNode> queue = new LinkedList<>();//定义一个对列，用来存放结点
        queue.offer(root);//如果不是空树，将根节点放入队列当中
        while(!queue.isEmpty()){//当队列不为空时，进入循环
            TreeNode cur = queue.poll();//定义一个cur，用来记录弹出队列的元素
            if(cur != null){//如果弹出队列的元素不为空
                queue.offer(cur.left);//则将弹出队列的左右孩子结点，放入队列当中
                queue.offer(cur.right);
            }else{//如果弹出队列的元素为空
                break;//则直接结束
            }
        }
        //判断队列当中的剩余元素，
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();//用tmp记录弹出队列的元素
            if (tmp != null) {//如果弹出队列的元素不为空，则返回false，则这个二叉树不是完全二叉树
                return false;
            }
        }
        return true;//将队列中的元素遍历完，也没有遇到非空元素，则这个二叉树为完全二叉树
    }
    //非递归实现 前序遍历
    public void preOrderNor(TreeNode root){
        if (root == null) {
            return ;
        }
        TreeNode cur = root;//定义一个跑腿引用，用来代替root遍历二叉树
        Deque<TreeNode> stack = new ArrayDeque<>();//定义栈，存放每个子树根节点
        while(cur != null || stack.isEmpty()) {
            while (cur != null) {//如果根节点不为空，则进入循环
                stack.push(cur);//将cur指向的根节点放入栈中
                System.out.println(cur.val + " ");//并且将其数值打印
                cur = cur.left;//然后在遍历根节点的左子树
            }
            TreeNode top = stack.pop();//如果根节点为空，弹出栈顶元素，用top记录
            cur = top.right;//cur指向弹出元素的右子树
        }
    }
    //中序遍历的非递归实现
    public void inOrderNor(TreeNode root){
        if (root == null) {
            return ;
        }
        TreeNode cur = root;//定义一个跑腿引用，用来代替root遍历二叉树
        Deque<TreeNode> stack = new ArrayDeque<>();//定义栈，存放每个子树根节点
        while(cur != null || stack.isEmpty()) {
            while (cur != null) {//如果根节点不为空，则进入循环
                stack.push(cur);//将cur指向的根节点放入栈中
                cur = cur.left;//然后在遍历根节点的左子树
            }
            TreeNode top = stack.pop();//如果根节点为空，弹出栈顶元素，用top记录
            System.out.println(top.val + " ");//并且将其数值打印
            cur = top.right;//cur指向弹出元素的右子树
        }
    }
    //后序遍历的非递归实现
    public void postOrderNor(TreeNode root){
        if (root == null) {
            return ;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.println(top.val+" ");
                stack.pop();
                prev = top;
            }else{
                cur = top.right;
            }
        }
        System.out.println();
    }
}
